#include <iostream>
#include <typeinfo>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
void set_test()
{
    #if 0
    //去重+升序排序
    set<int> s;
    //去重+降序排序(给一个大于的仿函数)
    //set<int,greater<int>> s;
    //入值
    s.insert(5);
    s.insert(2);
    s.insert(7);
    s.insert(5);
    //迭代器遍历
    set<int>::iterator it = s.begin();
    while(it != s.end())
    {
        cout << *it << " ";
        it++;
    }
    cout << endl;
    //插入一端initializer_list列表值,已经存在的值插入失败
    s.insert({2,8,3,9});
    for(auto& e : s)
    {
        cout << e << " ";
    }
    cout << endl;

    set<string> strset = {"sort","insert","add"};
    //遍历string比较Ascii码大小顺序遍历的
    for(auto& e : strset)
    {
        cout << e << " ";
    }
    cout << endl;
    #endif

    #if 0
    //删除
    set<int> s = {4,2,7,2,8,5,9};
    for(auto& e : s)
    {
        cout << e << " ";
    }
    cout << endl;
    //删除最小值
    s.erase(s.begin());
    //删除最大值
    //s.erase(--s.end());
    for(auto& e : s)
    {
        cout << e << " ";
    }
    cout << endl;
    //输入值删除
    // int x(0);
    // cin >> x;
    // int num(s.erase(x));
    // if(num == 0)
    // {
    //     cout << x << "不存在" << endl;
    // }
    // for(auto& e : s)
    // {
    //     cout << e << " ";
    // }
    // cout << endl;
    //利用迭代器删除
    int y(0);
    cin >> y;
    set<int>::const_iterator f = s.find(y);
    //cout << typeid(f).name() << endl;
    if(f != s.end())
    {
        s.erase(f);
    }
    else
    {
        cout << y << "不存在" << endl;
    }

    for(auto& e : s)
    {
        cout << e << " ";
    }
    cout << endl;
    //find
    //容器中的find和算法库的find
    //算法库的查找O(N)
    auto pos1 = find(s.begin(),s.end(),y);
    //set自身实现的查找O(logN)
    auto pos2 = s.find(y);
    //查找某个值在不在
    int z(0);
    cin >> z;
    if(s.count(z))
    {
        cout << z << "存在!" << endl;
    }
    else
    {
        cout << z << "不存在!" << endl;
    }
    #endif
    set<int> s = {10,20,35,40,50,65,70,80,90};
    for(auto& e : s)
    {
        cout << e << " ";
    }
    cout << endl;
    set<int>::iterator low = s.lower_bound(30);
    set<int>::iterator up = s.upper_bound(60);
    //删除
    s.erase(low,up);
    for(auto& e : s)
    {
        cout << e << " ";
    }
    cout << endl;
}
void multiset_test()
{
    //multi是排序,而不是去重
    multiset<int> ms({4,2,7,2,4,8,4,5,4,9,4 });
    //迭代器遍历
    multiset<int>::iterator it = ms.begin();
    while(it != ms.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    //相比set不同的是,x可能会存在多个,find查找的是中序的第一个
    int x = 0;
    cin >> x;
    multiset<int>::iterator pos = ms.find(x);
    while(pos != ms.end() && *pos == x)
    {
        cout << *pos << " ";
        pos++;
    }
    cout << endl;
    //相比set不同的是multiset中的count会返回实际个数
    cout << ms.count(x) << endl;
    //相比set不同的是,erase给值时会删除所有的x
    ms.erase(x);
    for(auto e : ms)
    {
        cout << e << " ";
    }
    cout << endl;
}
void map_test()
{
    #if 0
    //实现一个字典
    map<string,string> dict = {{"left","左边"},{"right","右边"},{"insert","插入"},{"string","字符串"}};
    //迭代器遍历
    map<string,string>::iterator it = dict.begin();
    while(it != dict.end())
    {
        //cout << (*it).first << ":" << (*it).second << endl;
        cout << it->first << ":" << it->second << endl;
        //cout << it.operator->()->first << ":" << it.operator->()->second << endl;
        it++;
    }
    cout << endl;
    //插入
    //insert插入pair对象的4种方式
    //1.插入一个pair对象
    pair<string,string> kv1("first","第一个");
    dict.insert(kv1);
    //2.插入一个匿名pair对象
    dict.insert(pair<string,string>("second","第二个"));
    //3.插入一个make_pair对象
    dict.insert(make_pair("sort","排序"));
    //C++11支持多参数隐式类型转换
    dict.insert({"auto","自动的"});
    //范围for遍历
    for(const auto& e : dict)
    {
        cout << e.first << ":" << e.second << endl;
    }
    cout << endl;
    //还支持这样遍历
    //C++17支持
    // for(const auto& [k,v] : dict)
    // {
    //     cout << k << ":" << v << endl;
    // }
    // cout << endl;
    string s;
    
    // while(cin >> s)
    // {
    //     map<string,string>::iterator f = dict.find(s);
    //     if(f != dict.end())
    //     {
    //         cout << "->" << " " << f->second << endl;;
    //     }
    //     else
    //     {
    //         cout << "该单词不存在,请重新输入" << endl;
    //     }
    // }
    cout << "*****************" << endl;
    //修改
    //迭代器遍历中也可以修改
    it = dict.begin();
    while(it != dict.end())
    {
        cout << it->first << ":" << it->second << endl;
        //first不可以修改,second可以
        //it->first += 'y';
        it->second += 'y';
        it++;
    }
    cout << endl;
    //范围for遍历
    for(const auto& e : dict)
    {
        cout << e.first << ":" << e.second << endl;
    }
    cout << endl;
    #endif
    //水果统计次数
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    map<string,int> m;
    for(const auto& e : arr)
    {
        m[e]++;
    }
    map<string,int>::iterator it = m.begin();
    while(it != m.end())
    {
        cout << it->first << ":" << it->second << endl;
        it++;
    }
    cout << endl;
    for(const auto& e : m)
    {
        cout << e.first << ":" << e.second << endl;
    }
    cout << endl;
}
//仿函数
template<class T>
struct Less
{
    bool operator()(const T& x,const T& y)
    {
        return x < y;
    }
};
template<class T>
struct Greate
{
    bool operator()(const T& x,const T& y)
    {
        return x > y;
    }
};
//打印函数 - 函数模板
template<class Container>
void Print(const Container& c)
{
    //迭代器遍历
    //typename Container::const_iterator it = c.begin();
    auto it = c.begin();
    while(it != c.end())
    {
        cout << *it << " ";
        it++;
    }
    cout << endl;
}
void SetTest()
{
    #if 0
    //array<int,10> arr = {8,4,10,2,5,3,9,1,7,6};
    array<int,10> arr = {18,14,20,12,15,13,19,11,17,16};
    //迭代器区间初始化
    //set<int> s(arr.begin(),arr.end());
    //拷贝构造
    //set<int> tmp(arr.begin(),arr.end());
    //set<int> s(tmp);
    //initializer_list初始化
    set<int,Less<int>> s({8,4,10,2,5,3,9,1,7,6});
    //迭代器遍历
    Print(s);
    //插入
    //插入一个值
    //s.insert(-1);
    //插入一段区间
    s.insert(arr.begin(),arr.end());
    Print(s);
    //插入initializer_list
    s.insert({28,24,30,22,25,23,29,21,27,26});
    Print(s);
    //给迭代器删除
    // int x(0);
    // cin >> x;
    // set<int>::iterator pos =  s.find(x);
    // if(pos != s.end())
    // {
    //     s.erase(pos);
    // }
    // else
    // {
    //     cout << "该值不存在!!!" << endl;
    // }
    // Print(s);
    //给值删除
    // int x(0);
    // cin >> x;
    // s.erase(x);
    // Print(s);
    #endif
    //erase的迭代器区间删除
    // set<int> s({10,20,35,40,50,60,75,80,90,100});
    // Print(s);
    // set<int>::iterator itlow = s.lower_bound(30);
    // set<int>::iterator itup = s.upper_bound(70);
    // s.erase(itlow,itup);
    // Print(s);
    //swap,交换函数
    // set<int> s1({1,2,3,4,5});
    // set<int> s2({6,7,8,9,10});
    // Print(s1);
    // Print(s2);
    // s1.swap(s2);
    // Print(s1);
    // Print(s2);
    //count的使用
    // set<int> s = {1,2,3,4};
    // cout << s.count(10) << endl;
    // set<int> s = {1,2,3,4,4,4,4,4,4};
    // Print(s);
    // cout << s.count(4) << endl;

}
void MultisetTest()
{
    multiset<int> ms({8,4,10,4,2,5,3,9,1,7,6,8,4,7,8,4,4});
    Print(ms);
    //查找 - find的查找的是中序的第一个
    int x(0);
    cin >> x;
    multiset<int>::iterator pos = ms.find(x);
    while(pos != ms.end() && *pos == x)
    {
        cout << *pos << " ";
        pos++;
    }
    cout << endl;
    //count
    cout << ms.count(x) << endl;
    //删除
    ms.erase(x);
    Print(ms);
}
//打印函数 - 函数模板
template<class Container>
void MapPrint(const Container& c)
{
    typename Container::const_iterator it = c.begin();
    while(it != c.end())
    {
        cout << it->first << ":" << it->second << endl;
        it++;
    }
    cout << endl;
}
void MapTest()
{
    //迭代器区间构造
    array<int,10> arr = {8,4,10,2,5,3,9,1,7,6};
    map<string,string,Less<string>> dict = {{"left","左边"},{"right","右边"}};
    MapPrint(dict);
}
int main()
{
    MapTest();
    return 0;
}